package com.kevin.Code.Array;

/**
 * @author Vinlee Xiao
 * @Classname Searcha2dMatrixii
 * @Description Leetcode 240. 搜索二维矩阵 II 中等难度 高频
 * @Date 2021/11/2 22:06
 * @Version 1.0
 */
public class Searcha2dMatrixii {

    /**
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        int row = matrix.length;
        int col = matrix[0].length;


        //先从0行开始遍历
        for (int i = 0; i < col; i++) {
            if (target == matrix[0][i]) {
                return true;
            }
//            System.out.println(matrix[0][i]);
            //只需要遍历第一行中target小于第一行中的数找出
            if (target < matrix[0][i]) {
                break;
            }

            //二分查找
            int low = 0;
            int high = row - 1;


            //遍历列
            while (low <= high) {
                int mid = (low + high) / 2;

                int tmp = matrix[mid][i];
                if (tmp == target) {
                    return true;
                } else if (tmp < target) {
                    low = mid + 1;
                } else if (tmp > target) {
                    high = mid - 1;
                }
            }
        }

        return false;
    }

    /**
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {

        int row = matrix.length;
        int col = matrix[0].length;

        int low = 0;
        int high = col - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (target == matrix[0][mid]) {
                return true;
            } else if (target > matrix[0][mid]) {
                low = mid + 1;
            } else if (target < matrix[0][mid]) {
                high = mid - 1;
            }
        }

        for (int i = 0; i <= high; i++) {
            //二分查找
            int l = 0;
            int h = row - 1;


            //遍历列
            while (l <= h) {
                int mid = (l + h) / 2;

                int tmp = matrix[mid][i];
                if (tmp == target) {
                    return true;
                } else if (tmp < target) {
                    l = mid + 1;
                } else if (tmp > target) {
                    h = mid - 1;
                }
            }
        }

        return false;
    }


    public static void main(String[] args) {
        int[][] nums = new int[][]{{1, 1}};
        Searcha2dMatrixii searcha2dMatrixii = new Searcha2dMatrixii();
        boolean b = searcha2dMatrixii.searchMatrix(nums, 1);
        System.out.println(b);
    }
}
